package com.devshephard.rpcframework.acm.tree.util;

import org.springframework.security.core.parameters.P;

public class DP_1 {

    public static void main(String[] args) {


        String str_1 = "aabdbbccababcc";

        String str_2 = "dbbabc";
        String str_3 = "aabccabc";


        boolean interleave = isInterleave("dbbabc", "aabccabc", "aabdbbccababcc");
        System.out.println(interleave);


    }


        public static boolean isInterleave(String s1, String s2, String s3) {
            if (s1.length() + s2.length() != s3.length()) {
                return false;
            }
            char[] c1 = s1.toCharArray();
            char[] c2 = s2.toCharArray();
            char[] c3 = s3.toCharArray();
            int n = c1.length;
            int m = c2.length;
            boolean[][] f = new boolean[n + 1][m + 1];
            for (int i = 0; i <= n; i++) {
                for (int j = 0; j <= m; j++) {
                    if (i == 0 && j == 0) {
                        f[0][0] = true;
                        continue;
                    }
                    if (i != 0) {
                        if (c1[i - 1] == c3[i + j - 1]) {
                            f[i][j] = f[i - 1][j];
                        }
                    }
                    if (f[i][j]) {
                        continue;
                    }
                    if (j != 0) {
                        if (c2[j - 1] == c3[i + j - 1]) {
                            f[i][j] = f[i][j - 1];
                        }
                    }
                }
            }

            return f[n][m];
        }
    }

  


